// 模拟
// 思路比较简单 - 直接根据题目要求进行模拟
// 一定要在演草纸上手动模拟算法流程，避免凭空想象
// 难度高的模拟题，往往都需要找规律，才能简化，否则代码不好写，并且时间/空间复杂度较高，

// 例题 3：
// 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
//
//        比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
//
//        P   A   H   N
//        A P L S I I G
//        Y   I   R
//        之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
//
//        请你实现这个将字符串进行指定行数变换的函数：
//
//        string convert(string s, int numRows);
//
//        示例 1：
//
//        输入：s = "PAYPALISHIRING", numRows = 3
//        输出："PAHNAPLSIIGYIR"
//        示例 2：
//        输入：s = "PAYPALISHIRING", numRows = 4
//        输出："PINALSIGYAHRPI"
//        解释：
//        P     I    N
//        A   L S  I G
//        Y A   H R
//        P     I
//        示例 3：
//
//        输入：s = "A", numRows = 1
//        输出："A"
//
//
//        提示：
//
//        1 <= s.length <= 1000
//        s 由英文字母（小写和大写）、',' 和 '.' 组成
//        1 <= numRows <= 1000

// 解题思路：
// 本题的难点在于找规律，确定每行字符的公差
// 首行和尾行的公差为 d = numRows * 2 - 2
// 中间行的公差也是 d，但是每行有两个字符，两个字符之间的关系为 index1 + index2 = d
// 如果这道题只有一行，那么就不需要变换了，直接返回 s 即可

public class Convert {
    public String convert(String s, int numRows) {
        if(numRows == 1) return s;
        int n = s.length();
        int d = 2 * numRows - 2;// 公差
        char[] ss = s.toCharArray();
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < n; i += d) ret.append(ss[i]);
        for(int i = 1; i < numRows - 1; i++){
            int index1 = i; int index2 = d - i;
            while(index1 < n || index2 < n){
                if(index1 < n) {
                    ret.append(ss[index1]);
                    index1 += d;
                }
                if(index2 < n){
                    ret.append(ss[index2]);
                    index2 += d;
                }
            }
        }
        for(int i = numRows - 1; i < n; i += d) ret.append(ss[i]);
        return ret.toString();
    }
}
